package com.kexinxin.util.matching;

import java.util.LinkedList;
import java.util.List;

import com.kexinxin.bean.Skill;
import com.kexinxin.service.impl.MatchingDAOImpl;
import com.kexinxin.service.impl.SearchDAOImpl;



public class BN {
	static int maxNumber;
	static int[][] result;
	public static void kruskal(int n, int e, EdgeNode[] E, EdgeNode[] t) {
		Heap H = new Heap();
		for (int i = 0; i < e; i++) {
			H.put(E[i]);
		}
		UnionFind U = new UnionFind(n + 1);

		int k = 0;
		while (e > 0 && k < n - 1) {
			EdgeNode x = (EdgeNode) H.pop();
			e--;
			int a = U.find(x.u);
			int b = U.find(x.v);
			if (a != b) {
				t[k++] = x;
				U.union(a, b);
			}
		}
	}
	
	public BN(){
		List<EdgeNode> edgeNodeList = MatchingDAOImpl.getEdgeNodeList();

		EdgeNode[] E1 = new EdgeNode[edgeNodeList.size()];
		for (int i = 0; i < edgeNodeList.size(); i++) {
			E1[i] = edgeNodeList.get(i);
		}

		EdgeNode[] t1 = new EdgeNode[MatchingDAOImpl.getNodeNumber()];
		maxNumber = MatchingDAOImpl.getNodeMaxNumber();
		kruskal(maxNumber, edgeNodeList.size(), E1, t1);
		int[][] graph = new int[maxNumber + 1][maxNumber + 1];
		for (int i = 0; i < maxNumber + 1; i++) {
			for (int j = 0; j < maxNumber + 1; j++) {
				graph[i][j] = -1;
			}
		}
		for (int i = 0; i < t1.length - 1; i++) {
			graph[t1[i].u][t1[i].v] = t1[i].weight;
			graph[t1[i].v][t1[i].u] = t1[i].weight;
		}
		
		Algorithm_DFS dfs = new Algorithm_DFS(graph);
		result = dfs.DFS(graph);
	}
	
	public static void show(EdgeNode[] e) {
		int count = 0;
		for (int i = 0; i < e.length - 1; i++) {
			System.out.println("link node  " + e[i].u + " and node  " + e[i].v);
			count += e[i].weight;
		}
		System.out.println(count);
	}

	public  List<Skill> matchingResult(String skillname) {

		

		List<Skill> matchingList = new LinkedList<Skill>();
		int next = SearchDAOImpl.getSkillIdByName(skillname);
		// System.out.println(next);
		getResultList(maxNumber, result, matchingList, next);
		return matchingList;

	}

	public static void getResultList(int maxNumber, int[][] result, List<Skill> matchingList, int next) {

		while (next != -1 && next < maxNumber) {
			int max = -1;
			// System.out.println(next);
			Skill skill = new Skill();
			String name = SearchDAOImpl.getSkillNameById(next);
			skill.setSkillId(next);
			skill.setSkillName(name);
			matchingList.add(skill);
			for (int j = 0; j < maxNumber + 1; j++) {
				if (result[next][j] != -1) {
					if (max < j) {
						max = j;
					}
				}
			}
			next = max;
		}
	}
}
